Thực đơn
Cây đỏ đen Các phép toán trên cây đỏ đenCó thể áp dụng ngay các phép chèn, xóa trong cây tìm kiếm nhị phân vào cây đỏ đen mà không cần sửa chữa gì vì cây đỏ đen là trường hợp riêng của cây tìm kiếm nhị phân. Tuy nhiên, khi đó có thể có một số tính chất trong định nghĩa của cây đỏ đen sẽ bị vi phạm. Việc khôi phục các tính chất đỏ đen sẽ cần một số nhỏ cỡ O(log n) hoặc trung bình chỉ O(1) các phép đổi màu (tốn rất ít thời gian) và không quá ba phép quay cho phép xóa, hai cho phép chèn. Toàn bộ các giải thuật chèn và xóa có độ phức tạp thời gian cỡ O(log n).
Phép chèn bắt đầu bằng việc bổ sung một nút như trong cây tìm kiếm nhị phân bình thường và gán cho nó màu đỏ. Ta xem xét để bảo toàn tính chất đỏ đen từ các nút lân cận với nút mới bổ sung. Thuật ngữ nút chú bác sẽ dùng để chỉ nút anh (hoặc em) với nút cha của nút đó như trong cây phả hệ. Chú ý rằng:
Mỗi trường hợp được giới thiệu bằng một đoạn mã C. Nút chú bác và nút ông dễ dàng xác định nhờ các hàm sau:
struct node *grandparent(struct node *n) { return n->parent->parent;}
struct node *uncle(struct node *n) { if (n->parent == grandparent(n)->left) return grandparent(n)->right; else return grandparent(n)->left;}
Trường hợp 1: Nút mới thêm N ở tại gốc. Trong trường hợp này, gán lại màu đen cho N, để bảo toàn tính chất 2 (Gốc là đen). Vì mới chỉ bổ sung một nút, Tính chất 5 được bảo đảm vì mọi đường đi chỉ có một nút.
void insert_case1(struct node *n) { if (n->parent == NULL) n->color = BLACK; else insert_case2(n);}
Trường hợp 2: Nút cha P của nút mới thêm là đen, khi đó Tính chất 4 (Cả hai nút con của nút đỏ là đen) không bị vi phạm vì nút mới thêm có hai con là "null' là đen. Tính chất 5 cũng không vi phạm vì nút mới thêm là đỏ không ẩnh hưởng tới số nút đen trên tất cả đường đi.
void insert_case2(struct node *n) { if (n->parent->color == BLACK) return; /* Tree is still valid */ else insert_case3(n);}Chú ý: Trong trường hợp tiếp theo nếu N có ông là nút G, vì nếu cha P là đỏ và P không ở gốc thì G là đen. Như vậy, N cũng có chú bác là U, although it may be a leaf in cases 4 and 5.
void insert_case3(struct node *n) { if (uncle(n)!= NULL && uncle(n)->color == RED) { n->parent->color = BLACK; uncle(n)->color = BLACK; grandparent(n)->color = RED; insert_case1(grandparent(n)); } else insert_case4(n);}Chú ý: Trong các trường hợp tiếp theo, giả sử rằng nút cha P là con trái của cha của nó. Nếu nó là con phải, left và right đổi chỗ cho nhau trong cases 4 and 5.
Diagram of case 4 Trường hợp 4: Nút cha P là đỏ nhưng nút chú bác U là đen, nút mới N là con phải của nút P, và P là con trái của nút G. Trong trường hợp này, thực hiện quay trái chuyển đổi vai trò của nút mới N và nút cha P do đó định dạng lại nút P bằng Trường hợp 5 (đổi vai trò N và P) vì tính chất 4 bị vi phạm (Cả hai con của nút đỏ là đen). Phép quay cũng làm thay đổi một vài đường đi (các đường đi qua cây con nhãn "1") phải đi qua thêm nút mới N, nhưng vì N là đỏ nên không làm chúng vi pham tính chất 5 |
void insert_case4(struct node *n) { if (n = = n->parent->right && n->parent = = grandparent(n)->left) { rotate_left(n->parent); n = n->left; } else if (n = = n->parent->left && n->parent = = grandparent(n)->right) { rotate_right(n->parent); n = n->right; } insert_case5(n);}
void insert_case5(struct node *n) { n->parent->color = BLACK; grandparent(n)->color = RED; if (n == n->parent->left && n->parent == grandparent(n)->left) { rotate_right(grandparent(n)); } else { /* Here, n == n->parent->right && n->parent == grandparent(n)->right */ rotate_left(grandparent(n)); }}
Trong cây tìm kiếm nhị phân bình thường khi xóa một nút có cả hai con (không là lá null), ta tìm phần tử lớn nhất trong cây con trái hoặc phần tử nhỏ nhất trong cây con phải, chuyển giá trị của nó vào nút đang muốn xóa (xem Cây tìm kiếm nhị phân). Khi đó chúng ta xóa đi nút đã được copy giá trị, nút này có ít hơn hai con (không là lá null). Vì việc copy giá trị không làm mất tính chất đỏ đen nên không cần phải sửa chữa gì cho thao tác này. Việc này chỉ đặt ra khi xóa các nút có nhiều nhất một con (không là lá null).
Chúng ta sẽ thảo luận về việc xóa một nút có nhiều nhất một con (không là lá null).
Nếu ta xóa một nút đỏ, ta có thể chắc chắn rằng con của nó là nút đen. Tất cả các đường đi đi qua nút bị xóa chỉ đơn giản bớt đi một nút đỏ do đó tính chất 5 không thay đổi. Ngoài ra, cả nút cha và nút con của nút bị xóa đều là nút đen, do đó tính chất 3 và 4 vẫn giữa nguyên..Một trường hợp đơn giản khác là khi xóa một nút đen chỉ có một con là nút đỏ. Khi xóa nút đó các tính chất 4 và 5 bị phá vỡ, nhưng nếu gán lại màu cho nút con là đen thì chúng lại được khôi phục.
Trường hợp phức tạp xảy ra khi cả nút bị xóa và nút con của nó đều là đen. Chúng ta sẽ bắt đầu bằng việc thay nút bị xóa bằng nút con của nó. Chúng ta sẽ gọi nút con này (trong vị trí mới của nó là N, và anh em với nó (con khác của nút cha mới) là S.Tiếp theo ta vẫn dùng P chỉ cha mới của N, SL chỉ con trái của S, và SR chỉ con phải của S (chúng tồn tại vì S không thể là lá).
Chú ý: Giữa các trường hợp khác nhau, vai trò và nhãn của các nút có thể thay đổi, nhưng trong một trường hợp mọi nhãn giữ vai trò không thay đổi. Trong hình vẽ các màu đỏ đen được thể hiện khi màu của nút đã rõ ràng, màu trắng biểu thị một màu chưa rõ (hoặc đỏ hoặc đen).Chúng ta sẽ sử dụng hàm sau tìm người anh em của N':
struct node *sibling(struct node *n) {if (n = = n->parent->left) return n->parent->right;else return n->parent->left;}Chú ý: Tất nhiên, chúng ta cần hoàn chỉnh các lá null sau mọi phép thay đổi. Nếu nút bị xóa không có con N khác "lá null", dễ dàng thấy rằng các tính chất được thỏa mãn. Còn nếu N là một "lá nulll", có thể sửa chữa lược đồ (hoặc code) để trong tất cảc các trường hợp các tính chất được thỏa mãn.
Trước mỗi bước ta có thể dùng hàm (function) replace_node
thay thế nút con child
vào vị trí của nút bị xóa trên cây. Để thuận tiện các đoạn code trong mục này quy ước rằng các "lá null" được biểu diễn bằng các đối tượng nút thực sự khác biệt một chút với NULL (code trong phép chèn có biểu diễn không nư vậy).
void delete_one_child(struct node *n) { /* Giả thiết: n có ít nhất một nút con null */ struct node *child = is_leaf(n->right) ? n->left: n->right; replace_node(n, child); if (n->color == BLACK) { if (child->color == RED) child->color = BLACK; else delete_case1(child); } free(n);}Ghi chú: Nếu N là "lá nul" và ta khong muốn biểu diễn các "lá null" bằng các đối tượng nút thực, ta có thể sửa giải thuật bằng cách trước hết gọi delete_case1() trên cha của nó (nghĩa là nút bị xóa
n
trong đoạn code trên) rồi sau đó mới xóa nó. Ta có thể làm như vậy vì cha của nó là đen, do đó có diễn biến như với "lá null" (một số người gọi là "lá ảo", "lá ma"). Ta cũng có thể xóa nó khỏi cuối của n
và sẽ khôi phục lại sau tất cả các phép toán.Nếu cả N và gốc ban đầu của nó là đen thì sau khi xóa các đường qua "N" giảm bớt một nút đen. Do đó vi phạm Tính chất 5, cây cần phải cân bằng lại. Có các trường hợp sau:
Trường hợp 1: N là gốc mới. Trong trường hợp này chúng ta dừng lại. Ta đã giải phóng một nút đen khỏi mọi đường đi và gôc mới lại là đen. Không tính chất nào bị vi phạm.
void delete_case1(struct node *n) { if (n->parent == NULL) return; else delete_case2(n);}Chú ý: Trong các trường hợp 2, 5, và 6, ta quy ước N là con trái của cha P. Nếu no là con phải, left và right sẽ tráo đổi cho nhau. Tuy nhiên code ví dụ làm cho cả hai trường hợp.
Diagram of case 2 Trường hợp 2: S là đỏ. Trong trường hợp này tráo đổi màu của P và S, và sau đó quay trái tai P, nó sẽ làm cho S trở thành nút ông của N. Chú ý rằng P có màu đen và có một con màu đỏ. Tất cả các đường đi có số các nút đen giống nhau, bây giờ N có một anh em màu đen và cha màu đỏ, chúng ta có thể tiếp tục với các trường hợp 4, 5, hoặc 6. (anh em mới của nó là đen ví chỉ có một con của nút đỏ S.)Trong các trường hợp sau la sẽ gọi anh em mới của N' là S. |
void delete_case2(struct node *n) { if (sibling(n)->color == RED) { n->parent->color = RED; sibling(n)->color = BLACK; if (n == n->parent->left) rotate_left(n->parent); else rotate_right(n->parent); } delete_case3(n);}
void delete_case3(struct node *n) { if (n->parent->color == BLACK && sibling(n)->color == BLACK && sibling(n)->left->color == BLACK && sibling(n)->right->color == BLACK) { sibling(n)->color = RED; delete_case1(n->parent); } else delete_case4(n);}
Trường hợp 4: S và các con của S là đen nhưng P là đỏ. Trong trường hợp này, chúng ta đổi ngược màu của S và P. Điều này không ảnh hưởng tới số nút đen trên các đường đi không qua N, nhưng thêm một nút đen trên các đường đi qua N, thay cho nút đen đã bị xóa trên các đường này.
void delete_case4(struct node *n) { if (n->parent->color == RED && sibling(n)->color == BLACK && sibling(n)->left->color == BLACK && sibling(n)->right->color == BLACK) { sibling(n)->color = RED; n->parent->color = BLACK; } else delete_case5(n);}
Trường hợp 5: S là đen, con trái của S là đỏ, con phải của S là đen, còn N là con trái của cha nó. Trong trường hợp này chúng ta quay phải tại S, khi đó con trái của S trở thành cha của S và N là anh em mới của nó. Sau đó ta tráo đổi màu của S và cha mới của nó.Tất cả các đường đi sẽ có số nút đen như nhau, nhưng bây giờ N có một người anh em đen mà con phải của nó lại là đỏ, chúng ta chuyển sang Trường hợp 6. Hoặc N hoặc cha của nó bị tác động bởi việc dịch chuyên này.
(Lưu ý trong trường hợp 6, ta đặt lại nút anh em mới của N là S.)
void delete_case5(struct node *n) { if (n == n->parent->left && sibling(n)->color == BLACK && sibling(n)->left->color == RED && sibling(n)->right->color == BLACK) { sibling(n)->color = RED; sibling(n)->left->color = BLACK; rotate_right(sibling(n)); } else if (n == n->parent->right && sibling(n)->color == BLACK && sibling(n)->right->color == RED && sibling(n)->left->color == BLACK) { sibling(n)->color = RED; sibling(n)->right->color = BLACK; rotate_left(sibling(n)); } delete_case6(n);}
void delete_case6(struct node *n) { sibling(n)->color = n->parent->color; n->parent->color = BLACK; if (n == n->parent->left) { /* Here, sibling(n)->right->color == RED */ sibling(n)->right->color = BLACK; rotate_left(n->parent); } else { /* Here, sibling(n)->left->color == RED */ sibling(n)->left->color = BLACK; rotate_right(n->parent); }}
Nhắc lại rằng các hàm này có lời gọi đệ quy. Thêm nữa lời gọi không đệ quy sẽ được goi sau một phép quay, do đó số lần thực hiện các phép quay là không đổi (không quá 3).
Thực đơn
Cây đỏ đen Các phép toán trên cây đỏ đenLiên quan
Cây Cây sáo thần Cây họ đậu Cây trồng biến đổi gen Cây cứt lợn Cây táo nở hoa Cây gạo Cây lương thực Cây tìm kiếm nhị phân Cây sự sốngTài liệu tham khảo
WikiPedia: Cây đỏ đen https://commons.wikimedia.org/wiki/Category:Red-bl...